package ljl.alg.wangzheng_camp.round1.bisection;

public class _34_first_and_last_pos {
    
    /**
     * 写这么长，有点笨逼啊
     * */
    public int[] searchRange3(int[] nums, int target) {
        int r = searchRight(nums, target);
        if (r == -1) return new int[]{-1, -1};
        return new int[] {searchLeft(nums, target), r};
    }
    
    int searchRight(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int res = -1;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            if (nums[mid] <= target) {
                if (nums[mid] == target) res = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return res;
    }
    int searchLeft(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int res = -1;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            if (nums[mid] >= target) {
                if (nums[mid] == target) res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }
    
    /**
     * 一个佬给出的解法
     * 解决了我多年的疑惑，必须写写不然就忘了
     * */
    public int[] searchRange2(int[] nums, int target) {
        if (nums.length == 0) return new int[] {-1, -1};
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[l] != target) return new int[]{-1, -1};
        int resL = l;
        
        l = 0;
        r = nums.length - 1;
        while (l < r) {
            int mid = (l + r + 1) >>> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        return new int[] {resL, l};
    }
    
    /**
     * 官方解法
     * 骚套路
     * 真鸡巴怪这个判断写的，第 76 行
     * */
    public int[] searchRange4(int[] nums, int target) {
        int l = search(nums, target, true);
        int r = search(nums, target, false) - 1;
        if (l == nums.length || nums[l] != target) return new int[]{-1, -1};
        return new int[] {l, r};
    }
    int search(int[] nums, int t, boolean lower) {
        int l = 0, r = nums.length - 1;
        int res = nums.length;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            if (nums[mid] > t || lower && nums[mid] >= t) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }
    
}
